package leetcode.N1_N100;

/**
 * @author 歪大哥😁
 * @date 2020-06-23.
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 *  
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class N4 {

    public static void main(String[] args) {
        int[] nums1 = {1,2};
        int[] nums2 = {3,4};
        System.out.println(findMedianSortedArrays(nums1, nums2));

    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //merge两个数组成为一个数组
        return findMedianByArray(merge(nums1, nums2));
    }

    private static double findMedianByArray(int[] merge) {
        int length = merge.length;
        if ((length & 1) == 1) {
            return merge[(length) / 2];
        } else {
            return ((merge[length / 2 - 1] + merge[length / 2])) / 2d;
        }
    }

    private static int[] merge(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        if (length1 == 0) {
            return nums2;
        }
        int length2 = nums2.length;
        if (length2 == 0) {
            return nums1;
        }
        int[] num = new int[length1 + length2];
        int index1 = 0;
        int index2 = 0;
        int index = 0;
        boolean isNums1Empty = false;
        boolean isNums2Empty = false;
        for (;index < length1 + length2; index++) {
            if (isNums1Empty || isNums2Empty) {
                break;
            }
            if (nums1[index1] > nums2[index2]) {
                num[index] = nums2[index2++];
                if (index2 >= length2) {
                    isNums2Empty = true;
                }
            } else {
                num[index] = nums1[index1++];
                if (index1 >= length1) {
                    isNums1Empty = true;
                }
            }
        }
        if (isNums1Empty) {
            for (;index < length1 + length2; index++) {
                num[index] = nums2[index2++];
            }
        }
        if (isNums2Empty) {
            for (;index < length1 + length2; index++) {
                num[index] = nums1[index1++];
            }
        }
        return num;
    }
}
